package com.aqie.medium.heap;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * todo
 * 378  n x n 矩阵，其中每行和每列元素均按升序排序
 * 找到排序后第k小元素
 */
public class KthSmallest {
    /**
     * 1,最大堆 43ms
     * @param matrix
     * @param k
     * @return
     */
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        PriorityQueue<Integer> heap = new PriorityQueue<>(k, Comparator.reverseOrder());
        for (int[] aMatrix : matrix) {
            for (int j = 0; j < n; j++) {
                if (heap.size() < k) {
                    heap.add(aMatrix[j]);
                } else if (heap.peek() > aMatrix[j]) {
                    heap.poll();
                    heap.add(aMatrix[j]);
                }
            }
        }
        return heap.peek();
    }

    /**
     * 2,多路归并  klogk
     */
    public int kthSmallest2(int[][] matrix, int k) {
        if (matrix.length == 0) return 0;

        return 0;
    }

    /**
     * 3,二分查找 13ms
     */
    public int kthSmallest3(int[][] matrix, int k) {
        int row = matrix.length, col = matrix[0].length;
        int l = matrix[0][0], r = matrix[row-1][col-1];
        while(l <= r){
            int mid = (r-l)/2 + l;
            int count = 0;
            for (int i = 0; i < row; i++){
                for (int j = 0; j < col && matrix[i][j] <= mid; j++){
                    count++;
                }
            }
            if (count < k) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

    /**
     * 4,二分查找优化 2ms
     * @param matrix
     * @param k
     * @return
     */
    public int kthSmallest4(int[][] matrix, int k) {
        int n = matrix.length;
        int m = matrix[0].length;
        int low = matrix[0][0];
        int high = matrix[n-1][m-1];
        int count = 0;
        while (low < high) {
            int mid = low + (high - low)/2;
            int i = n-1;
            int j = 0;
            /* 二分搜索, 从左下角开始与 mid 进行比较 */
            count = 0;
            while (i >= 0 && j < m) {   /* leetcode: 240 */
                if(mid < matrix[i][j]) i--;
                else {
                    count += (i+1);
                    j++;
                }
            }
            if(count >= k) high = mid;
            else low = mid+1;
        }
        return low;
    }

    /**
     * 合并两个数组
     * @param a
     * @param b
     * @return
     */
    public static int[] merge(int[] a, int[] b) {
        int lena = a.length;
        int lenb = b.length;
        int[] c = new int[lena + lenb];
        int i = 0, j = 0, k = 0;//分别代表数组a ,b , c 的索引
        while (i < lena && j < lenb) {
            if (a[i] < b[j])
                c[k++] = a[i++];
            else
                c[k++] = b[j++];
        }
        while (i < lena)
            c[k++] = a[i++];
        while (j < lenb)
            c[k++] = b[j++];
        return c;
    }

    public static void main(String[] args) {
        int[] a = {1,  5,  9};
        int[] b = {10, 11, 13};
        System.out.println(Arrays.toString(merge(a, b)));
    }
}
